/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package logica.grafo;

import java.util.ArrayList;

/**
 *
 * @author aluno
 */
public class Dijkstra {

    private final int GRAPHSIZE = 2048;
    private final int INFINITY = GRAPHSIZE * GRAPHSIZE;
    private boolean visited[];
    private ArrayList<ArrayList<Integer>> path;

    public Dijkstra() {
        visited = new boolean[GRAPHSIZE];
        path = new ArrayList<ArrayList<Integer>>();
    }

    /**
     * 
     * @param source
     * @param destiny
     * @param d
     * @param dist
     * @param n
     * @return
     */
    public ArrayList<Integer> shortestPath(int source, int destiny, float[] d, float[][] dist, int n) {
        System.out.println("Partindo de \"" + source + "\" com destino a \"" + destiny + "\":");

         ArrayList<Integer> first = new ArrayList<Integer>();
         path.add(first);

        for (int i = 1; i <= n; i++){
            ArrayList<Integer> novo = new ArrayList<Integer>();
            path.add(novo);
            path.get(i).add(source);
        }

        int mini;

        /**
         * Seta o flag visited como zero para todos os nós
         */
        for (int i = 1; i <= n; ++i) {
            d[i] = INFINITY;
            visited[i] = false; /* o elemento i-esimo nao foi visitado ainda */
        }

        /**
         * Seta a distancia do ponto source para ele mesmo como zero
         */
        d[source] = 0;

        /**
         *
         */
        for (int k = 1; k <= n; ++k) {

            mini = -1;
            for (int i = 1; i <= n; ++i) {
                if (!visited[i] && ((mini == -1) || (d[i] < d[mini]))) {
                    mini = i;
                } // fim do if
            } // fim do for

            /*if(k == 1)
                System.out.println(mini);*/

            visited[mini] = true;

            for (int i = 1; i <= n; ++i) {
                if (dist[mini][i] != 0) {
                    if (d[mini] + dist[mini][i] < d[i]) {
                        d[i] = d[mini] + dist[mini][i];

                       //if (i == destiny) {
                        if (mini != source) {
                            path.get(i).add(mini);
                        }
                        //}

                        /*System.out.println("I: " + i);
                        System.out.println("MINI: " + mini);*/

                    }// fim do if
                }// fim do if
            }//fim do for
        }

        for(int i = 0; i < n; i++){
            path.get(i).add(i);
        }
        //System.out.println("Path = " + path);

        ArrayList<Integer> invertedPath = new ArrayList<Integer>();

        int lastElement = path.get(destiny).get(1);
        invertedPath.add(destiny);
        invertedPath.add(lastElement);

        while(true){
            //System.out.println("Entrou no while true.");
            if(path.get(lastElement).size() >= 3){
                lastElement = path.get(lastElement).get(1);
                //System.out.println("Path analisado: " + path.get(lastElement));
                invertedPath.add(lastElement);
                //System.out.println("invertedPath: " + invertedPath);
            }
            else if(path.get(lastElement).size() == 2){
                invertedPath.add(path.get(lastElement).get(0));
                break;
            }
        }

        ArrayList<Integer> realPath = new ArrayList<Integer>();
        realPath.add((int)d[destiny]);

        int tam = invertedPath.size();
        for(int i = 0; i < tam; i++){
            realPath.add(invertedPath.get(tam-1-i));
        }
        return realPath;
    }
}